#!/usr/bin/env python

__author__ = "lynn lin"
__lience__ = "MIT"
# import decimal module
from decimal import NaN

#class node(object):
#    def __init__(self,name,dis = NaN,parent = 0,visited = False):
#        self.name = name
#        self.dis = dis
#        self.parent = parent
#        self.visited = visited
        
class sort_collection(object):
    """
    sort class
    """
    def __init__(self,A=[]):
        self.data = A
        self.heapsize = len(A)
        
    # obj is node class instance    
    # use dis as comparison key
    
#    def cmp(self,obj1,obj2):
#        if  obj1.dis > obj2.dis :
#            return True
#        else:
#            return False
        
    def __left(self,i):
        return  (2*i + 1)

    def __right(self,i):
        return (2*i + 2)

    def __parent(self,i):
        return (i-1)/2
        
    def __max_heapify(self,i):
         l = self.__left(i)
         r = self.__right(i)
         if l < self.heapsize and self.data[l] > self.data[i]:
            largest = l
         else:  
            largest = i
         if r < self.heapsize and self.data[r] > self.data[largest]:
            largest = r
         if largest != i :
            self.data[i],self.data[largest] = self.data[largest],self.data[i]
            self.__max_heapify(largest)
            
    def __min_heapify(self,i):
         l = self.__left(i)
         r = self.__right(i)
         if l < self.heapsize and self.data[l] < self.data[i]:
            smallest = l
         else:  
            smallest = i
         if r < self.heapsize and self.data[r] < self.data[smallest]:
            smallest = r
         if smallest != i :
            self.data[i],self.data[smallest] = self.data[smallest],self.data[i]
            self.__min_heapify(smallest)
        
    def build_max_heapify(self):
        for i in range(len(self.data)/2,-1,-1):
            self.__max_heapify(i)
    def build_min_heapify(self):
        for i in range(len(self.data)/2,-1,-1):
            self.__min_heapify(i)

    def heapsort(self,mode = 1):
        """
        default sort order is ascending,if setting mode to 0,the sort order is descending
        """
        if mode == 1:
            self.build_max_heapify()
        else :
            self.build_min_heapify()
        length = len(self.data)
        for i in range(length-1,0,-1):
            self.data[i],self.data[0] = self.data[0],self.data[i]
            self.heapsize -= 1
            if mode == 1:
                self.__max_heapify(0)
            else:
                self.__min_heapify(0)
                
    def heap_maximum(self):
        return self.data[0]

    def heap_minimum(self):
        return self.data[0]

    def heap_extract_min(self):
        if self.heapsize < 1 :
            raise
        min = self.data[0]
        self.data[0] = self.data[self.heapsize-1]
        self.heapsize -= 1
        self.__min_heapify(0)
        return min
    
    def heap_extract_max(self):
        if self.heapsize < 1 :
            raise
        max = self.data[0]
        self.data[0] = self.data[self.heapsize-1]
        self.heapsize -= 1
        self.__max_heapify(0)
        return max
    
    def heap_increase_key(self,i,key):
        if key < self.data[i]:
            raise
        self.data[i] = key
        while i > 0 and self.data[self.__parent(i)] < self.data[i]:
            self.data[self.__parent(i)],self.data[i] = self.data[i],self.data[self.__parent(i)]
            i = self.__parent(i)
        
    def testfun():
        pass
    
if __name__ == '__main__':
    A=[1,7,5,0,2]
#    A=['v1','v2','v5','v3']
#    B=[]
#    x1 = node('v1',4,0,False)
#    x2 = node('v2',5,0,False)
#    x3 = node('v3',2,0,False)
#    x4 = node('v4',1,0,False)
#    B.append(x1)
#    B.append(x2)
#    B.append(x3)
#    B.append(x4)
    
    x = sort_collection(A)
    x.heapsort()
    print A 
   
